class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1)return 1;
        int dp[3];
        dp[0] = dp[1] = 1;
        int i = 1;
        while (--n)
        {
            i++;
            i %= 3;
            dp[i] = dp[(i + 1) % 3] + dp[(i + 2) % 3];
        }
        return dp[i];
    }
};